Mark Sweep GCについて
あとでブログに書き直す(かも)
スライドにして見てね
https://gyazo.com/5d94c76eab07a7b57ea0d0b3fb1e3140
大まかな目次
動機
短所への対策
用いられている言語の例
終わり
動機
この辺の本を読んでいる
https://images-na.ssl-images-amazon.com/images/I/51ihQN2UlbL._SX382_BO1,204,203,200_.jpg https://images-na.ssl-images-amazon.com/images/I/41S-zt1rBdL._SX258_BO1,204,203,200_.jpg
GC (Garbage Collection) とは
自動でメモリ上のゴミを回収し、再利用できるようにしてくれるやつ
主にヒープ上の話
メモリ界のこんまり
GCがないとどうなるか
手動でメモリを管理しないといけない
mallocとかfreeとかするやつ
起きそうな問題
メモリリーク
ダングリングポインタの参照
使用中のメモリの誤解放
GCのない言語
C, C++, Rust, etc.
モダンな言語にはだいたい入ってる
弱点もある
GC中はプログラムが停止する
stop the world
基礎的なGC
以下の4つが基本的なもの
Mark Sweep GC ← 今回話すやつ
Refeence Counting GC
Copying GC
Mark Compact GC
それ以外のGC
さっきの4つのいずれかの組み合わせ
割といっぱいある
etc.
Mark Sweep GC の話
Mark Sweep GCの概要
世界初のGC
2つのフェーズから成る
Mark Phase
Sweep Phase
Mark Phase
生きているオブジェクト全てにマークを付ける
深さ優先探索が用いられることが多い
キャッシュを利用をしやすい
メモリの使用効率が良い
生きているオブジェクトの数に比例して時間がかかる
手順
1. ルートから辿れるオブジェクトにマークを付ける
2. さらにそこから辿れるオブジェクトにマークを付ける
Sweep Phase
マークが付いていないオブジェクトを回収する
その後、マークが付いているものはマークを外す
ヒープのサイズに比例して時間がかかる
図で見てみよう
Aはルートオブジェクト
緑はマークを付けたオブジェクト
Work List はアルゴリズム上つかうもので、マーク付けてないやつをメモっておくもの
矢印は参照を表す
ポイントは深さ優先探索してるとことか
ex.
例えば以下の例ではオブジェクトAがBとGを参照している
https://gyazo.com/de131fe02d1bdd1695fb721a1ebc7696
https://gyazo.com/a33706194b64125cfbab5ec30770cf9a
Aはルートオブジェクト
https://gyazo.com/653254af8ab072785cb919e12bf5a709
https://gyazo.com/b12116c518ecd344a9025991c8c56fbe
深さ優先探索なのでGではなく、Cをマークした
Work ListにDとEをメモ
https://gyazo.com/de131fe02d1bdd1695fb721a1ebc7696
マークを付けたのでWork ListからDを消して、次のEを入れた
https://gyazo.com/445ae86948f3d245071de6c3e232d070
マークを付けたのでWork ListからEを消した
https://gyazo.com/e2ce1ec397e5f652a8d13a3560229742
一番深くまで来たので、上へ戻る
JとかLとかは辿れないので無視
https://gyazo.com/2b1f2c9da8fc6b8bb7172c64d5a3e85c
https://gyazo.com/38ff827f359e32b7587a35a7f0154bac
Hをマーク
HはGを参照しているが、すでにマークしているのでなにもしない
https://gyazo.com/2240c13d38e18edf63d39c80b819d5e1
Mark Phaseが終わった
この時点で絶対にWork Listは空になる
ここからSweep Phaseへ入る
https://gyazo.com/8afb39bf20fc290017dbea91cd9ed255
死んでるオブジェクトを回収してフリーリストに入れる
https://gyazo.com/467b7fdb8a807e9d90a7527031cf4bec
次のGCへ備えてマークを外しておいた
ここまでずっとStop the World状態
ここでやっとミューテータへ実行権を移す
さっきのスライドをもう一度見てみる
Mark Phase
生きているオブジェクト全てにマークを付ける
深さ優先探索が用いられることが多い
キャッシュを利用をしやすい
メモリの使用効率が良い
生きているオブジェクトの数に比例して時間がかかる
手順
1. ルートから辿れるオブジェクトにマークを付ける
2. さらにそこから辿れるオブジェクトにマークを付ける
Sweep Phase
マークが付いていないオブジェクトを回収する
その後、マークが付いているものはマークを外す
ヒープのサイズに比例して時間がかかる
Q. どこにマークすんねん
A. オブジェクトのヘッダの中です
ONかOFFなので1bitでいける
用語の説明
チャンク
フリーリスト
チャンクとは
「塊」という意味
初期状態はヒープ全体が一つのチャンク
「メモリくれ」って言われたら、ここから適切なサイズを切り出して渡す
チャンクを分割しすぎるとフラグメンテーションの原因になる
フリーリストとは
回収されたチャンクを管理する片方向リンクリスト
チャンクのサイズはばらばら
主にメモリアロケート時に使う話
「メモリくれ」と言われたら、この中から適切なサイズのチャンクを探して切り出して渡す
Mark Sweep GC の長所
実装が簡単
ミューテータの読み出し、書き出し操作にオーバーヘッドがかからない
Mark Phase のスループットが高い
ヒープの空間的使用量の効率が良い
保守的GCとの相性がいい
短所
フラグメンテーション起こりがち
アロケートのたびにフリーリストを探索するので時間がかかる
せっかくメモリ共有してるのにMark Phaseで生きてるオブジェクト全てにマークを付けるので不必要にコピーされまくる
短所への対策
Multiple free-list
Big Bag Of Pages(BiBOP法)
Bitmap Marking
Lazy Sweep
Multiple free-list
https://gyazo.com/3ad13e4b39fa1e9053aca5e90704bf07
チャンクのサイズごとにフリーリストを用意する
2ワード用、3ワード用、...、100ワード用、..、101ワード以上用の100個用意したり
フリーリストを全部探索する必要がなくなる
Big Bag Of Pages(BiBOP法)
https://gyazo.com/2dc738da4647cd0f858decf1fbd6bc7d
フラグメンテーションの対策
ヒープを固定サイズに分割して、似たサイズのオブジェクトをまとめて配置して管理する
サイズ以外にも型でわけたりもすることもある
Bitmap Marking
CoWの相性の悪さへの対策
マーキングの有無をオブジェクトのヘッダではなく、別の場所の2次元テーブルで管理する
Lazy Sweep
ミューテータの最大停止時間を減少させる
Sweep Phaseのスイープ処理を遅延して行う
アロケート時に必要なチャンクが見つかるまでスイープ操作を行う
用いられている言語の例
Ruby(MRI)
JavaScript
Go v1.10
C#
C, C++
Boehm GCが使える
Java
Objective-C
etc.(調べきれてない)
おわり
僕の部屋と机の上もGCしてほしい